/*
 	Tool for Path Finding Algorithm Testing (ToPFAT) 
 	
    Copyright (C) 2009, Teemu Turunen and Arttu Viljakainen 
    Published under GNU General Public License V3 
    (see http://www.gnu.org/licenses/licenses.html)
    
    This file is part of Tool for Path Finding Algorithm Testing.

    Tool for Path Finding Algorithm Testing is free software: you can 
    redistribute it and/or modify it under the terms of the GNU General 
    Public License as published by the Free Software Foundation, 
    either version 3 of the License, or (at your option) any later version.

    Tool for Path Finding Algorithm Testing is distributed in the hope that it
    will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General 
    Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Tool for Path Finding Algorithm Testing. If not, see         <http://www.gnu.org/licenses/>.
 */

package algorithms.dijkstra;

import graph.Graph;
import graph.LinkedNodeList;
import graph.Node;

import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

import algorithms.DescriptedPoint;
import algorithms.PathFindingAlgorithm;
import algorithms.SearchResult;

/**
 * Class to calculate paths in two dimensional array
 * using Dijkstra's algorithm. Not guaranteed to implement
 * the algorithm correctly.
 * 
 * See more about Dijkstra's algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
 * 
 * @author arttu viljakainen
 *
 */
public class DijkstraStyleAlgorithm implements PathFindingAlgorithm{
	
	private SearchResult searchResult;
	private NewDNode startNode;
	private NewDNode goalNode;
	private long searchTime;
	private Deque<DescriptedPoint> finalPath;
	private Deque<DescriptedPoint> finalUsedCells;
	private LinkedNodeList<NewDNode> dNodes;
	
	/**
	 * Finds the path and returns SearchResult.
	 */
	@Override
	public SearchResult findPath(Point start, Point goal, Graph graph) {
		if(start == null || goal == null || graph == null)
			return new SearchResult();
		
		searchResult = new SearchResult();
		dNodes = convertNodesToNewDNodes(graph.getNodes());
		
		startNode = dNodes.getNodeAt(start);
		startNode.setDistanceFromStart(0);
		goalNode = dNodes.getNodeAt(goal);
		
		long timeBeforeSearch = System.nanoTime();
		
		PriorityQueue<NewDNode> usedCells = calculateDistancesFrom(startNode, goalNode);
		PriorityQueue<NewDNode> path = calculateFinalPath(startNode, goalNode);
		
		searchTime = System.nanoTime() - timeBeforeSearch;
		long searchTimeInMillis = searchTime / 1000000;
		
		finalPath = new ArrayDeque<DescriptedPoint>();
		finalUsedCells = new ArrayDeque<DescriptedPoint>();
		int pathLength = path.size();
		while(! path.isEmpty()) {
			NewDNode node = path.remove();
			DescriptedPoint point = new DescriptedPoint(node.getLocation().x, node.getLocation().y);
			point.setDescription(
					"<html>" +
					"Path cell <br> " +
					"Distance from start " + (node.getDistanceFromStart() / 10) + "<br>" + 
					"Path cells " + (pathLength - 2) + "<br>" + 
					"Steps " + (pathLength - 1) + "<br>" +
					"Search time " + searchTimeInMillis + " ms " +
					"</html>");
			finalPath.add(point);
		}
		while(! usedCells.isEmpty()) {
			NewDNode node = usedCells.remove();
			DescriptedPoint point = new DescriptedPoint(node.getLocation().x, node.getLocation().y);
			point.setDescription("<html>" +
					"Visited cell <br> " +
					"Distance from start " + (node.getDistanceFromStart() / 10) + 
					"</html>");
			finalUsedCells.add(point);
		}
		
		searchResult.setPath(finalPath);
		searchResult.setUsedCandidates(finalUsedCells);
		searchResult.setTimeInNanoseconds(searchTime);
		
		return searchResult;
	}
	
	public LinkedNodeList<NewDNode> convertNodesToNewDNodes(LinkedNodeList<Node> nodes) {
		LinkedNodeList<NewDNode> dNodes = new LinkedNodeList<NewDNode>();
		for(Node node : nodes) {
			dNodes.add(new NewDNode(node));
		}
		
		for(Node node : nodes) {
			NewDNode dNode = dNodes.getNodeAt(node.getLocation());
			for(Node neigh : node.getNeighbours()) {
				dNode.addNeighbour(dNodes.getNodeAt(neigh.getLocation()));
			}
		}
		
		return dNodes;
	}
		
	/**
	 * Returns the neighbour with shortes path to the start.
	 * 
	 * @param node
	 * @return Node with shortest path to the start
	 */
	private NewDNode getBestNeighbourOf(NewDNode node) {
		NewDNode best = null;
		for(Node dn : node.getNeighbours()) { // TODO Ugly and buggy
			if(best == null || ((NewDNode)dn).getDistanceFromStart() < best.getDistanceFromStart()) {
				best = (NewDNode)dn;
			}
		}
		
		return best;
	}
		
	/**
	 * Calculates distances from the start for all nodes until finds the goal.
	 * Returns all visited cells.
	 * 
	 * @param startNode
	 * @param goalNode
	 * @return Visited cells.
	 */
	private PriorityQueue<NewDNode> calculateDistancesFrom(NewDNode startNode, NewDNode goalNode) {
		PriorityQueue<NewDNode> nodes = new PriorityQueue<NewDNode>();
		LinkedList<NewDNode> stack = new LinkedList<NewDNode>();
		stack.add(startNode);
		nodes.add(startNode);
		
		while(! stack.isEmpty()) {
			NewDNode master = stack.poll();
						
			for(Node node : master.getNeighbours()) { // TODO Ugly and buggy
				if(((NewDNode)node).getDistanceFromStart() > (master.getDistanceFromStart() + distanceBetweenNeighbours(master.getLocation(), node.getLocation()))) {
					((NewDNode)node).setDistanceFromStart(master.getDistanceFromStart() + distanceBetweenNeighbours(master.getLocation(), node.getLocation()));
				}
				if(! nodes.contains(node)) {
					NewDNode d = (NewDNode)node;
					stack.add(d);
					nodes.add(d);
				}
			}
			if(nodes.contains(goalNode))
				return nodes;
		}
		return nodes;
	}
	
	/**
	 * Returns the distance between neighbours.
	 * 
	 * @param node1
	 * @param node2
	 * @return distance
	 */
	private int distanceBetweenNeighbours(Point node1, Point node2) {
		if(node1.x == node2.x || node1.y == node2.y)
			return 10;
		else 
			return 11;
	}
		
	/**
	 * Calculates the final path using valuated nodes.
	 * 
	 * @param start
	 * @param goal
	 * @return Final path
	 */
	private PriorityQueue<NewDNode> calculateFinalPath(NewDNode start, NewDNode goal) {
		PriorityQueue<NewDNode> path = new PriorityQueue<NewDNode>();
		if(goal.getDistanceFromStart() == Integer.MAX_VALUE)
			return path;
		NewDNode next = goal;
		
		while(! next.equals(start)) {
			path.add(next);
			next = getBestNeighbourOf(next);
		}
		
		path.add(next);
		
		return path;
	}
		
	@Override
	public String toString() {
		return "Dijkstra-style";
	}

}
